package code;

import java.util.ArrayList;
import java.util.List;
public class DetectCycle_day07 {
    public static void main(String[] args) {
        ListNode head = new ListNode(0);head.next = null;
        ListNode temp1= new ListNode(1);head.next = temp1;
        ListNode temp2= new ListNode(2);temp1.next = temp2;
        ListNode temp3= new ListNode(3);temp2.next = temp3;
        ListNode temp4= new ListNode(4);temp3.next = temp4;
        ListNode temp5= new ListNode(5);temp4.next = temp5;
        temp5.next = temp3;
//        0-1-2-3-4-5---3
        ListNode result = detectCycle(head);
        if (result != null) {
            System.out.println(result.val);
        }else {
            System.out.println("No cycle");
        }
    }
    public static ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        boolean is_cycle=false;
        //是否有环路
        while (fast != null && slow != null) {
            if (slow.equals(fast)) {
                is_cycle=true;
                break;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        //如果有环路，则寻找开始节点
        //遍历一遍后，第二次遍历的第一个节点就是开始节点
        if(is_cycle){
            List<ListNode> list=new ArrayList<>();
            ListNode p=head;
            while (p!=null){

                if(list.contains(p)){
                    return p;
                }
                else {
                    list.add(p);
                }
                p=p.next;
            }
        }
        return null;
    }
    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
